// https://leetcode.cn/problems/gas-station/

// 算法思路总结：
// 1. 遍历每个加油站作为起点尝试环形路线
// 2. 计算每个站点的净收益（加油量-消耗量）
// 3. 累计净收益为负时跳过当前起点区间
// 4. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) 
    {
        int m = gas.size();

        vector<int> diff(m);
        for (int i = 0 ; i < m ; i++)
            diff[i] = gas[i] - cost[i];

        for (int i = 0 ; i < m ; )
        {
            bool check = true;
            int sum = 0, step = 0;
            for ( ; step < m ; step++)
            {
                int cur = (i + step) % m;
                sum += diff[cur];

                if (sum < 0)
                {
                    i += step + 1;
                    check = false;
                    break;
                }
            }
            if (check) return i;   
        }
        return -1;
    }
};

int main()
{
    vector<int> v11 = {1,2,3,4,5}, v12 = {3,4,5,1,2};
    vector<int> v21 = {2,3,4}, v22 = {3,4,3};
    Solution sol;

    cout << sol.canCompleteCircuit(v11, v12) << endl;
    cout << sol.canCompleteCircuit(v21, v22) << endl;

    return 0;
}
